<table width="100%"><tr><td width="20%">
<a href="../index.html">&lt; index</a><br />
<a href="../fov/index.html">&lt; 12. Field of view toolkit</a>
</td><td width="60%">
<p align="center">
=====================================<br />
13. Path finding<br />
=====================================<br />
</p></td><td width="20%">
<a href="../bsp/index.html">&gt; 14. BSP toolkit</a>
</td></tr></table>
<style type="text/css">
.code { color:#444444; background-color:#EEEEEE;}
pre { color:#444444; background-color:#EEEEEE;}
table.param td { border : 1px solid #000000; }
th { background-color: #44BBFF; color: #FFFFFF }
table.none td { border : 0 }
</style>
This toolkit allows to easily calculate the optimal path between two points in your dungeon by using either the <a href="http://en.wikipedia.org/wiki/A*">A* algorithm</a> or <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">Dijkstra's algorithm</a>.<br />
<br />
Please note that the paths generated with the two algorithms may differ slightly. Due to how they're implemented, A* will usually prefer diagonal moves over orthogonal, while Dijkstra will have the opposite preference. In other words, paths from point X to point Y will look like this:<br />
<pre class="code">
A*:         Dijkstra:
..........  ..........
.X........  .X****....
..*.......  ......*...
...*......  .......*..
....****Y.  ........Y.
..........  ..........
</pre>
<a href="path_init.html">13.1 Creating a path</a><br />
<a href="path_compute.html">13.2 Computing the path</a><br />
<a href="path_get.html">13.3 Reading path information</a><br />
<a href="path_delete.html">13.4 Destroying a path</a><br />
<br />
